Denis S. Kokorev - Doctoral Student, Laboratory of Distributed Computational Systems, Institute for Information Transmission Problems RAS    
Address: 19, build.1, Bolshoy Karetny Per., Moscow, 127051, Russian Federation
E-mail: korvin-d@yandex.ru

      The article discusses the problem of finding a polyhedron given shape inside another nonconvex polyhedron. This problem is a particular case of the 18th Hilbert problem, third part. It has a practical application in computer simulation of three-dimensional objects, moving autonomous robots, and the jewelry industry. The author uses this mathematical problem to find the facets of gemstones in uncut stones.
      The article offers a method for finding inscribed polyhedrons based on the reduction of the problem to a nonlinear programming problem and its solutions using ready-made software. The basic idea is that it is easy to describe this problem in terms of non-linear programming.  Internal polyhedron volume is an objective function. Restrictions include the preservation of the combinatorial structure, one polyhedron standing inside another one, convexity, plus additional constraints necessary for practical purposes.
      The article describes two implementations of the algorithm: a client-server application and a local application. Their advantages and disadvantages are discussed. The algorithm is described not only in a mathematical point of view; some of its practical characteristics are also demonstrated. Compared to the previous article, the author has added a method that allows for solving the nonconvex case of a problem. This is a significant step forward from a mathematical point of view. In addition, it allows us to use the algorithm at all stages of gem cutting. The end of the article describes current evaluations of the effectiveness and running time, including on weak processors, and it offers plans for further development of the algorithm.

This research was supported by the Russian Scientific Foundation (project No. 16-11-10352